package interview;

import java.util.Arrays;

/**
 * @author zhangjie
 */
public class HeapTest2 {

  public static void main(String[] args) {
    HeapTest2 heapTest = new HeapTest2();
    int[] a = new int[]{0, 4, 3, 1, 6, 2, 7, 8, 23, 5, 6, 1, 56, 6};
    //bad case     int[] a = new int[]{0,4,3,1,6,2,7,8,23,5,6,1,56,6};
    heapTest.buildHeap(a);
    System.out.println(Arrays.toString(a));
  }

  //建立堆
  public int[] buildHeap(int[] a) {
    int len = a.length;
    int start = len / 2;
    while (start >= 0) {
      heapfiy(a, start, len);
      start--;
    }
    return a;
  }

  //堆化
  public void heapfiy(int[] a, int start, int n) {
    while (start < n) {
      int maxPosition = start;

      if (start * 2 + 1 < n && a[start * 2 + 1] > a[start]) {
        maxPosition = start * 2 + 1;
      }
      if (start * 2 + 2 < n && a[start * 2 + 2] > a[maxPosition]) {
        maxPosition = start * 2 + 2;
      }
      if (maxPosition == start) {
        break;
      }
      swap(a, maxPosition, start);
      start = maxPosition;
    }
  }

  public void swap(int[] a, int i, int j) {
    int tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
  }


}
